package com.my.sort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 * Created by Scarlett on 2018/10/8 .
 * <p>
 * 合并排序
 */
public class MergeSorter<T extends Comparable<T>> implements Sortable<T> {
    private static final Logger LOGGER = LoggerFactory.getLogger(MergeSorter.class);

    @Override
    public T[] sort(T[] elements) {
        if (elements == null || elements.length < 2) {
            return elements;
        }

        mergeSort(elements, 0, elements.length - 1);

        return elements;
    }

    private void mergeSort(T[] elements, int left, int right) {
        if (left == right) {
            return;
        }

        int middle = left + (right - left) / 2;

        //对左半部分数组元素进行合并排序
        mergeSort(elements, left, middle);

        //对右半部分数组元素进行合并排序
        mergeSort(elements, middle + 1, right);

        T[] copies = Arrays.copyOfRange(elements, left, right + 1);
        int i = left;
        int j = middle + 1;
        for (int k = left; k <= right; k++) {
            if (i > middle) {
                elements[k] = copies[j - left];
                j++;
                continue;
            }

            if (j > right) {
                elements[k] = copies[i - left];
                i++;
                continue;
            }

            if (copies[i - left].compareTo(copies[j - left]) > 0) {
                elements[k] = copies[j - left];
                j++;
            } else {
                elements[k] = copies[i - left];
                i++;
            }
        }

        LOGGER.info("left: {}, middle: {}, right: {}, elements: {}", left, middle, right, elements);
    }
}
